In computer networks, information is constantly being moved from a source to a destination, typically in the form of packets. In the simplest situations, the source and destination are directly connected and the packet of information passes from the source to the destination, without any intermediate stages. However, in most networks, there are at least one, if not multiple, intermediate stages between the source and the destination. In order for the information to move from the source to the destination, it must be routed through a set of devices that accept the packet and pass it along a predetermined path toward the destination. These devices, referred to generically as switches, are typically configured to accept packets from some number of input ports and transmit that information to an output port, which was selected from a plurality of ports. Often, ports are capable of both receiving and transmitting, such that the input and output ports are the same physical entities.
In an ideal network, traffic arrives at an input port of a switch. The switch determines the appropriate destination for the packet and immediately transmits it to the correct output port. In such a network, there is no need for storing the packet of information inside the switch, since the switch is able to transmit the packet as soon as it receives it.
However, because of a number of factors, this ideal behavior is not realizable. For instance, if the switch receives packets on several of its input ports destined for the same output port, the switch must store the information internally, since it cannot transmit all of these different packets of information simultaneously to the same output port. Similarly, an output port may become “congested”. This term describes the situation in which the device to which this output port is connected is unable to receive additional information for some reason. In such a case, the switch must store the packet destined for that output port internally until either the offending device is able to receive more information or the packet is discarded.
This need to store information within a switch requires that memory, or buffers, exist within the device to store the packet until it can be delivered. In order to organize this buffer space, queues are created. Queues are memory structures that implement a first in, first out protocol for the transmission of packets. In one implementation, each output port has an associated queue. When the switch receives information on an input port, it determines the destination and moves it to the appropriate output port queue. If the output port is not busy, then the information will be transmitted immediately. If the output port is congested, then the information will be placed at the end of the queue, and will have to wait its turn before being transmitted. Typically, the preferred objective is to transmit the information of a particular traffic class in the order in which it was received.
It is not necessary that a queue be associated with each output port. For example, a queue can be associated with each input port, such that information is immediately placed into a queue upon arrival. Later, the information is removed from the queue and transferred to the appropriate output port when that port is available.
However, these schemes suffer from a phenomenon known as Head-Of-Line (HOL) blocking. This refers to the situation where a queue continues to be filled with new packets of information, but is unable to transmit any information because the packet at the head of the list cannot be transmitted at the present time. Since queues function using a first in, first out priority, no other information can be sent until the packet at the head of the queue has been transmitted. For example, suppose that there are five packets in a queue for transmission, each destined for a different output port. Due to a situation downstream, output port 3 is unable to send at this time. Once the packet that is destined for output port 3 reaches the head of the queue, all progress stops until output port 3 is no longer congested. Therefore, a packet contained further down in the queue, which could have been sent on its associated output port, is blocked by the congestion on output port 3.
To help alleviate this problem, the input port can be configured with a queue for each output port. For example, if there are 16 output ports, each input port would have 16 queues associated with it; one per output queue. Such an arrangement reduces the HOL blocking issue described above, by adding additional storage at each input port. In this manner, information destined for output port 2 would not be blocked by congestion at output port 3. While this scheme reduces the issue of HOL blocking as compared to the previous scheme, the issue is not eliminated by this scheme, as described later.
While the information destined for a specific output port can be transmitted without reliance on the status of other output ports, there are still situations where HOL blocking occurs. In many cases, the output port of a switch is not connected to the final destination, but rather to another switch of similar or identical structure and behavior as the current switch. Thus, packets transmitted via output port 3 may arrive at a second switch, which then must repeat the process of determining the next destination. Suppose that output port 7 of this second switch is congested. Once this occurs, the second switch will no longer be able to accept additional information that is destined for its output port 7. Referring back to the first switch, the first switch maintains a queue for information destined for its output port 3 (i.e. the second switch). Once a packet destined for output port 7 of the second switch appears at the head of its queue for output port 3, the queue will become blocked because the second switch cannot accept any traffic destined for this port. Consequently, all other traffic destined for the second switch is blocked until output port 7 of the second switch has been cleared of its congestion. Thus, traffic destined for all other output ports on the second switch are unnecessarily blocked because of an isolated issue on one output port of the second switch.
HOL blocking is a serious concern in the development of networks. HOL blocking can reduce the overall used bandwidth by as much as 44%. Therefore, a solution is needed to further reduce the problem described above.
In some networks, a switch only has the ability to understand and determine which output port it should transmit a packet to; it has no ability to determine the path of the packet once it leaves that output port. However, some networks are designed so that the entire path of the packet is contained within the packet information, typically within a control header. In these cases, a switch is able to determine its actions for a particular packet of information, and is also able to determine what actions downstream switches will take.
Using this information, it is possible that a switch can further reduce the issue of HOL blocking. Previously, the queues were established to correspond to the output ports of the current switch. By increasing the number of queues to correspond to not only the output port of this switch, but also the output port of the next switch, the HOL blocking issue described above is alleviated. While this scheme significantly reduces the HOL blocking issue by looking at both the current output port and the next output port, it is very complex to implement.
If each switch has 16 potential output ports, then the number of queues associated with each input port grows from 16 in the scenario earlier described to 256. This number is determined by looking at each output queue and realizing that each output port has 16 potential next output ports. Therefore, there is a non-linear increase in the amount of queues that must be used to implement this improved scheme. In another example, if each switch has 32 output ports, then the number of queues per input port grows from 32, to 32*32 or 1024.
While the HOL issue is significantly reduced, the amount of queues and buffering that must be added to a switch to implement this scheme becomes prohibitive.
Therefore, it is an object of the present invention to provide a switch that offers the advantages of the improved scheme above, but does not require the high number of queues and buffers needed to implement it.